//题目:
// 给定一个正整数 n ，你可以做如下操作：
// 如果 n 是偶数，则用 n / 2替换 n 。
// 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
// 返回 n 变为 1 所需的 最小替换次数 。

// 示例 1：
// 输入：n = 8
// 输出：3
// 解释：8 -> 4 -> 2 -> 1

// 示例 2：
// 输入：n = 7
// 输出：4
// 解释：7 -> 8 -> 4 -> 2 -> 1
// 或 7 -> 6 -> 3 -> 2 -> 1

// 示例 3：
// 输入：n = 4
// 输出：2
 
// 提示：
// 1 <= n <= 231 - 1
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
    unordered_map<int,int> dp;
public:
    int integerReplacement(int n) 
    {
        // //1.创建dp表————dp[i]表示：将数i变为1的最小替换次数   n==INT_MAX：超出内存限制
        // vector<int> dp(n+2);
        // //2.初始化
        // dp[1]=0;
        // //3.填表————动态转移方程：if(i%2==0)dp[i]=1+dp[i/2]; else dp[i]=1+dp[i-1];
        // for(int i=2;i<=n+1;i++)
        // {
        //     if(i%2==0)
        //     {
        //         dp[i]=1+dp[i/2];
        //         dp[i-1]=min(dp[i-1],1+dp[i]);
        //     }
        //     else dp[i]=1+dp[i-1];
        // }
        // //4.确定返回值
        // return min(dp[n],1+dp[n+1]);

        //法二：记忆化搜索
        if(n==1) return 0;

        if(dp.count(n)) return dp[n];

        if(n%2==0) return 1+integerReplacement(n/2);

        dp[n]=2+min(integerReplacement((n-1)/2),integerReplacement(n/2+1));
        return dp[n];
    }
};